class Solution {
public:
    bool isPalindrome(string s) {
        int left = 0, right = s.size() - 1;
        while (left < right)
        {
            while (left < right && !(isalpha(s[left]) || isdigit(s[left])))
                ++left;
            while (left < right && !(isalpha(s[right]) || isdigit(s[right])))
                --right;

            if (tolower(s[left]) != tolower(s[right]))
                return false;

            ++left;
            --right;
        }

        return true;
    }
};

class Solution {
public:
    bool isSubsequence(string s, string t) {
        if (s.size() == 0 && t.size() == 0)
            return true;
            
        int s_pos = 0, t_pos = 0;
        for (; t_pos < t.size(); ++t_pos)
        {
            if (s[s_pos] == t[t_pos])
                ++s_pos;
            if (s_pos == s.size())
                return true;
        }
        
        return false;
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for (int left = 0, right = numbers.size() - 1; left < right;)
        {
            int sum = numbers[left] + numbers[right];
            if (sum > target)
                --right;
            else if (sum < target)
                ++left;
            else
                return vector<int>{left + 1, right + 1};
        }

        return vector<int>();
    }
};

class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans = 0;
        int left = 0, right = height.size() - 1;
        while (left < right)
        {
            int deep = min(height[left], height[right]);
            int width = right - left;
            ans = max(ans, deep * width);

            if (height[left] < height[right]) 
                ++left;
            else
                --right;
        }

        return ans;
    }
};

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());

        vector<vector<int>> ans;

        for (int i = 0; i < nums.size(); ++i)
        {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;

            int left = i + 1, right = nums.size() - 1;
            while (left < right)
            {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0)
                {
                    ans.push_back(vector<int>{nums[i], nums[left], nums[right]});

                    while (left < right && nums[left] == nums[++left]);
                    while (left < right && nums[right] == nums[--right]);
                }

                else if (sum > 0)
                    --right;
                else
                    ++left;
            }
        }

        return ans;
    }
};

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int min_len = INT_MAX;
        int sum = 0;
        for (int slow = 0, fast = 0; fast < nums.size(); ++fast)
        {
            sum += nums[fast];

            while (slow <= fast && sum >= target)
            {
                min_len = min(min_len, fast - slow + 1);
                sum -= nums[slow++];
            }
        }

        return min_len == INT_MAX ? 0 : min_len;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128]{0};
        int ans = 0;
        for (int slow = 0, fast = 0; fast < s.size(); ++fast)
        {
            ++hash[s[fast]];

            while (hash[s[fast]] > 1)
                --hash[s[slow++]];

            ans = max(ans, fast - slow + 1);
        }
        
        return ans;
    }   
};

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        int wordsLen = 0;
        unordered_map<string, int> hash1;
        for (auto& word : words)
        {
            wordsLen += word.size();
            hash1[word]++;
        }

        if (s.size() < wordsLen)
            return vector<int>();

        vector<int> ans;
        int s_len = s.size(), word_len = words[0].size();
        for (int i = 0; i < word_len; ++i)
        {
            unordered_map<string, int> hash2;
            for (int slow = i, fast = i + word_len; fast <= s_len; fast += word_len)
            {
                string temp = s.substr(fast - word_len, word_len);
                hash2[temp]++;
                while (hash2[temp] > hash1[temp])
                {
                    --hash2[s.substr(slow, word_len)];
                    slow += word_len;
                }

                if (fast - slow  == wordsLen)
                    ans.push_back(slow);
            }
        }
        
        return ans;
    }
};

class Solution {
public:
    string minWindow(string s, string t) {
        if (t.size() > s.size())
            return string();

        int len = INT_MAX, begin = 0;   //记录最小覆盖子串的长度和起始位置
        int hash1[128]{0};
        int hash2[128]{0};

        for (auto& ch : t)
            ++hash1[ch];

        for (int slow = 0, fast = 0, cnt = 0; fast < s.size(); ++fast)
        {
            //入窗口
            ++hash2[s[fast]];

            //cnt表示s中有效字符的个数
            //如果hash1[s[fast]] >= hash2[s[fast]]，那么说明fast所在的字符就是一个有效字符
            if (hash1[s[fast]] >= hash2[s[fast]])
                ++cnt;

            //如果有效字符的个数等于t的长度，就开始记录结果
            //之所以用循环，是因为题目求的是最短覆盖子串
            while (cnt == t.size())
            {
                if (fast - slow + 1 < len)
                {
                    len = fast - slow + 1;
                    begin  = slow;
                }
                
                //如果slow所在的字符是有效字符，那么这个字符出窗口后就需要--cnt
                if (hash2[s[slow]] <= hash1[s[slow]])
                    --cnt;
                
                --hash2[s[slow++]];
            }
        }

        return len == INT_MAX ? string() : s.substr(begin, len);
    }
};